#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll ct(ll a,ll b){
    ll res=0;
    ll t=0;
    while(a||b){
        if(a&1&&b&1)res+=(1<<t);
        t++;
        a>>=1;
        b>>=1;
    }
    return res;
}

void solve(){
    ll n,m;
    cin>>n>>m;
    ll temp=0;
    for(ll i=30;i>=0;i--){
        if(n>=(1<<i)*m){
            n-=(1<<i)*m;
            temp+=(1<<i);
        }
    }
    ll t=temp+(n>0);
    int res=ct(t,temp);
    cout<<res<<'\n';
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int _=1;
	cin>>_;
	while(_--){
		solve();
	}
	return 0;
}
